package solutions.leetcode.normal

import java.util.PriorityQueue

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/mice-and-cheese/">2611. 老鼠和奶酪</a>
 */
private class Solution2611 {
    fun miceAndCheese(reward1: IntArray, reward2: IntArray, k: Int): Int {
        val queue = PriorityQueue<Pair<Int, Int>> { o1, o2 -> (o1.first - o1.second) - (o2.first - o2.second) }
        var rst = 0
        for (i in reward1.indices) {
            queue.offer(Pair(reward1[i], reward2[i]))
            if (queue.size > k) {
                rst += queue.poll().second
            }
        }
        while (queue.isNotEmpty()) {
            rst += queue.poll().first
        }
        return rst
    }
}

fun main() {
    println(Solution2611().miceAndCheese(
        intArrayOf(
            1,1,3,4
        ),
        intArrayOf(
            4,4,1,1
        ),
        2
    ))
}